public class code {
    //找到子串在主串当中的下标
    public static int KMP(String str,String sub,int pos) {
        if(str == null||sub == null) return -1;

        int lenStr = str.length();
        int lenSub = sub.length();
        if(lenStr == 0||lenSub == 0) return -1;

        if(pos<0 || pos >= lenStr) return -1;

        int [] next = new int[lenSub];
        getNext(sub,next);

        int i = pos;//从pos位置开始遍历主串
        int j = 0;//遍历子串

        while(i < lenStr && j <lenSub) {
            //这里要考虑到一开始就不匹配，j=-1
            if (j==-1||str.charAt(i) == sub.charAt(j)) {
                i++;
                j++;
            } else {
                //下标不一样，一直回退
                j = next[j];
            }
        }
        if(j==lenSub) {
            return i-j;
        }
        return -1;

    }
    //重点：求子串的next数组
    public static void getNext(String sub,int [] next) {
        next[0] = -1;
        next[1] = 0;
        int i = 2;//i表示所求next数组的下标，是提前走了一步的
        int k = 0;//比较是否相等的前一项的k
        //这里next[i]就是要求的，和我们分析的next[i+1]一样
        // 原来判断的是p[i]==p[k]，现在应该判断p[i-1]==p[k]
        while(i < sub.length()) {
            //此处要考虑k回退到了-1位置，next值就为0
            if (k==-1||sub.charAt(i-1) ==sub.charAt(k)) {
                next[i] = k+1;
                k++;
                i++;
            } else {
                //p[i-1]！=p[k]，则k继续回退
                k = next[k];
            }
        }
    }


    public static void main(String[] args) {
        System.out.println(KMP("ababcabcdacbdeabcdef","abcd",0));
    }
}
